package com.example.leetcode.trainingcamp.week7.Thursday;

/**
 * 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
 *
 * <p>返回转换后的单向链表的头节点。
 *
 * <p>注意：本题相对原题稍作改动
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binode-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer17_12 {

    TreeNode head = new TreeNode(Integer.MAX_VALUE);
    TreeNode tail = head;

    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) return null;
        reverse(root);
        return head.right;
    }

    public void reverse(TreeNode root){
        if (root == null) return;
        reverse(root.left);
        TreeNode right = root.right;
        tail.right = root;
        tail = root;
        root.left = null;
        reverse(right);
    }
}
